// Copyright 2010-2012, Vanya Davidenko.
// Используемая кодировка: UTF-8.

#ifndef LIBV_SET_RECOGNIZER_H_
#define LIBV_SET_RECOGNIZER_H_

#include <assert.h>
#include <deque>
#include <set>
#include <string>
#include <vector>
#include <libv/check.h>



namespace libv {

/** Класс компилирует множество ASCII-строк в детерменированный конечный автомат
  * и за линейное время определяет принадлежность некоторой строки ему.
  * Поддерживается 2 режима: учитывающий регистр букв и игнорирующий его. */
class SetRecognizer {
  public:
    typedef int StateID;

  private:
    typedef int CharID;
    typedef ::std::vector<StateID> State;
    typedef ::std::deque<State> Dfa;

    enum { NUM_ASCII_CHARS = 128, INVALID_STATE_ID = -1, INVALID_CHAR_ID = -1 };

  public:
    typedef ::std::string Word;
    typedef ::std::set<Word> WordsSet;

    SetRecognizer()
      : factorization_table_(size_t(NUM_ASCII_CHARS), INVALID_CHAR_ID) {
        InitDfa();
    }

    SetRecognizer(const WordsSet& words, const bool case_sensitive = false)
      : factorization_table_(size_t(NUM_ASCII_CHARS), INVALID_CHAR_ID) {
        BuildCharTable(words, case_sensitive);
        InitDfa();
        BuildDfa(words);
    }


    bool Check(const Word& word) const {
        return Check(word.data(), word.size());
    }

    template<typename TAsciiChar>
    bool Check(const TAsciiChar* word, const ::std::ptrdiff_t word_size) const {
        return IsFinal(Process(word, word_size));
    }


    template<typename TAsciiChar>
    StateID Process(const TAsciiChar* word,
                    const ::std::ptrdiff_t word_size) const {
        LIBV_PRECOND(word != NULL);
        LIBV_PRECOND(word_size >= 0);

        if ( word_size == 0 ) {
            return 0;
        }

        StateID state_id = 0;
        for ( const TAsciiChar* i = word ; i - word != word_size ; ++i ) {
            if ( Factorize(*i) == INVALID_CHAR_ID ||
                 dfa_[state_id][Factorize(*i)] == INVALID_STATE_ID ) {
                return INVALID_STATE_ID;
            }

            state_id = dfa_[state_id][Factorize(*i)];
        }
        return state_id;
    }


    bool IsFinal(const StateID state_id) const {
        LIBV_PRECOND(state_id < static_cast<StateID>(final_states_.size()));

        if ( state_id == INVALID_STATE_ID ) {
            return false;
        }

        return final_states_[state_id];
    }


    size_t num_state_ids() const {
        return dfa_.size();
    }


  private:
    char SwitchLetterCase(const char c) const {
        assert(0 <= c && c < NUM_ASCII_CHARS);

        if ( 'a' <= c && c <= 'z' ) {
            return c - 'a' + 'A';
        } else if ( 'A' <= c && c <= 'Z' ) {
            return c - 'A' + 'a';
        }
        return c;
    }

    char LetterInLowerCase(const char c) const {
        assert(0 <= c && c < NUM_ASCII_CHARS);

        if ( 'A' <= c && c <= 'Z' ) {
            return c - 'A' + 'a';
        }
        return c;
    }


    ::std::deque<bool> UsedCharacters(const WordsSet& words) const {
        ::std::deque<bool> used_chars(NUM_ASCII_CHARS, false);

        for ( WordsSet::const_iterator \
              i = words.begin() ; i != words.end() ; ++i ) {
            for ( Word::const_iterator j = i->begin() ; j != i->end() ; ++j ) {
                assert(0 <= *j && *j < NUM_ASCII_CHARS);
                used_chars[*j] = true;
            }
        }
        return used_chars;
    }


    void BuildCharTable(const WordsSet& words, const bool case_sensitive) {
        ::std::deque<bool> used_chars = UsedCharacters(words);

        for ( size_t i = 0 ; i != used_chars.size() ; ++i ) {
            if ( used_chars[i] ) {
                const int index = static_cast<int>(chars_.size());
                if ( case_sensitive ) {
                    chars_.push_back(static_cast<char>(i));
                    factorization_table_[i] = index;

                } else {
                    const char c = SwitchLetterCase(static_cast<char>(i));
                    if ( factorization_table_[c] == INVALID_CHAR_ID ) {
                        chars_.push_back(LetterInLowerCase(c));
                        factorization_table_[i] = index;
                        factorization_table_[c] = index;
                    }
                }
            }
        }
    }


    template<typename TAsciiChar>
    CharID Factorize(const TAsciiChar c) const {
        if ( c < 0 || c >= NUM_ASCII_CHARS ) {
            return INVALID_CHAR_ID;
        }

        return factorization_table_[c];
    }


    StateID NewState() {
        State state;
        state.reserve(chars_.size());
        state.resize(chars_.size(), INVALID_STATE_ID);

        dfa_.push_back(state);
        return static_cast<StateID>(dfa_.size() - 1);
    }


    void MakeStateFinal(const StateID state_id) {
        assert(final_states_.size() <= dfa_.size());
        final_states_.resize(dfa_.size(), false);
        final_states_[state_id] = true;
    }


    void InitDfa() {
        assert(dfa_.empty());
        NewState();
        final_states_.resize(1, false);
    }


    void BuildDfa(const WordsSet& words) {
        assert(dfa_.empty() == false);
        for ( WordsSet::const_iterator \
              i = words.begin() ; i != words.end() ; ++i ) {
            AddWordToDfa(*i);
        }
    }


    void AddWordToDfa(const Word& word) {
        StateID state_id = 0;
        for ( Word::const_iterator i = word.begin() ; i != word.end() ; ++i ) {
            if ( dfa_[state_id][Factorize(*i)] == INVALID_STATE_ID )
                dfa_[state_id][Factorize(*i)] = NewState();

            state_id = dfa_[state_id][Factorize(*i)];
        }

        MakeStateFinal(state_id);
    }


    // Векторы лучше на кэш лягут.
    ::std::vector<int> factorization_table_;  // char -> CharID
    ::std::vector<char> chars_;  // CharID -> char

    Dfa dfa_;
    ::std::deque<bool> final_states_;
};

}  // libv

#endif  // LIBV_SET_RECOGNIZER_H_
